/**
 * 堆排序
 *      1:创建一个大顶堆,大顶堆得堆顶一定是最大得元素
 *      2:交换第一个元素和最后一个元素,让剩余得元素继续调整为大顶堆
 *      3:从后往前以此和第一个元素交换并重新构建 排序完成
 */
function heapSort (array) {
    crateHeap(array)
    console.log(array)
    //交换第一个元素和最后一个元素 然后重新调整大顶堆
    for (let i = array.length - 1; i > 0; i--) {
        [array[i], array[0]] = [array[0], array[i]]
        adjust(array, 0, i)
    }
    return array
}

//构建大顶堆,从第一个非叶子节点开始 进行下沉操作
function crateHeap (array) {
    const len = array.length
    const start = parseInt(len / 2) - 1
    for (let i = start; i >= 0; i--) {
        adjust(array, i, len)
    }
}
//将target个元素进行下沉 孩子节点有比他大得就下沉
function adjust (array, target, len) {
    for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
        //找到孩子节点中最大的
        if (i + 1 < len && array[i + 1] > array[i]) {
            i = i + 1
        }
        //下沉
        if (array[i] > array[target]) {
            [array[i], array[target]] = [array[target], array[i]]
            target = i
        } else {
            break;
        }
    }
}
let res = heapSort([2, 4, 9, 1, 3])
console.log(res)